/***************************************************************************
 *    Copyright (C) Catedra de structuri de date 
 *   
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

/**
 * @author: Cristian Talau
 * @file: binarytree.h
 * @brief This header file contain the user interface with a binary tree structure
 * 
 *   Contains data structures, functions for creeating, initializing a node or a tree, and for
 * detroying,  manipulating and traversing it. 
 */

#ifndef _BINARY_TREE_
#define _BINARY_TREE_


#include <stdio.h>
#include <malloc.h>




/**
 * @brief Types of traversing a binary tree:
 */



#define PREORDER 	0
#define INORDER 	1
#define POSTORDER 	2

/*
 * The NULL constant in this file: When a BT object in uninitialized, it must be BT_NULL
 */


#define BT_NULL         ( (BT_Node)0 )	

/*
 * Constants for choosing sons of a node
 */

#define LEFT   	 0
#define RIGHT  	 1
#define INVALID -1




struct _BT_Node;

/**
 *  @brief The data structure which represents a node of a binary tree. 
 *    It has as members,  an array of 2 pointers to his childs, a pointer to his father, and 
 * The data is stored using a void pointer which shoul be casted to which data type the user
 * wants to store in the tree. The structre BT_Sons is a vector which can contain sons of a node. 
 *  @see BT_NewNode(), BT_FreeNode()   
 */

typedef struct _BT_Node * BT_Node;
typedef BT_Node * BT_Sons;
 
/**
 * @brief The data structure which re[resents a binary tree, and it's related methods.
 * The structure contains the tree's root, and two 'pointer to function' members. 
 * The alloc member is used when we want to add more members to a node.
 * In this case, alloc returns a pointer to a zone of memory where resides a strcuture which
 *   contain at it's start the BT_Node structure, and then more members. 
 * The dealloc member is used to free the data stored in each node of the binary tree. By 
 *  default, this member is NULL, and the user must do all memory menagement. Most commonly you 
 *  want to set it 'free'. 
 *  The BT_Task is a tipe of function which can be applied to a BT_Node in a Tree Traversal.
 * In order to store nodes it's root needs to be initialized by BT_NewRoot().
 * @see BT_New(), BT_Free(), BT_FreeNode(), BT_NewAllocator(),BT_Traverse() 
 */

typedef BT_Node( *BT_Allocator)(void);
typedef int ( *BT_Deallocator)(void *);

struct BinaryTree_adt;

typedef struct BinaryTree_adt * BinaryTree;
typedef void (* BT_Task)(BT_Node );

/**
 *  @brief Creates an empty tree, with allocator and deallocator not set. 
 *   The elements will de created with BT_NewNode(). To set the tree's parameters, another two
 * constructors are available. Un arbore se distruge cu BT_Free(). 
 * @see BT_NewRoot(), BT_NewAllocator, BT_Free()
 *   
 */
BinaryTree BT_New(void);

/**
 * @brief Creates a new node and links it with the rest of the tree. 
 *  @param bt The tree where the node lives
 *  @param data The data which will be stored in the node
 *  @param left The left son of the new node
 *  @param right The right node of the new node
 *  @param parent The parent of the new node   
 *  @param dir  The direction in wich the new node will be his father's son.     
 *   The memory for the node will be allocated with the tree's alloc function, hence, if you
 * need a different structure (different from BT_Node) to be kept as the node, you must define
 * the alloc function furst. 
 *  @return The new created node
 */
BT_Node BT_NewNode( BinaryTree bt, void * data, BT_Node left, BT_Node right, BT_Node parent, int dir);

/**
 *  @brief Initialize the root of a tree.
 *  @param tr The tree which root you want to initialize
 *  @param root The node which will be placed in the root of the tree
 *  @pre  The root needs to be an initizlized node. 
 *  @return If the tr is BT_NULL this function create a new tree which returnes, else it returns
 * the first argument whith the root changed
 * @see BT_New() , BT_NewNode()
 */
BinaryTree BT_NewRoot(BinaryTree tr, BT_Node root);

/**
 * @brief Initizalize the allocator, and deallocator to a givent tree
 * If the tree is BT_NULL this will create a tree, set it's members and return it.
 */
BinaryTree BT_NewAllocator(BinaryTree a, BT_Allocator alloc, BT_Deallocator dealloc);


/**
 * @brief Free's a tree, and the data stored in each node if the deallocator is set so.
 * @warning If the deallocator is not set, you must free the memory for data previously
 */
void BT_Free(BinaryTree a);
/**
 * @brief Frees a node and the information stored in it split it from the tree given.
 *  @return Sons of the freed node. 
 */
BT_Sons BT_FreeNode(BinaryTree tr, BT_Node nd);

/**
 * Now follows member acces functions which purpose is quite simple
 */

/**
 * @return 1 if the node is root, 0 if it is not, or INVALID if it is uninitialized 
 */
int  BT_Root(BT_Node a);

/**
 *  @return 1 if the node is leaf, 0 if not , INVALID id it is uninitialized
 */
int BT_Leaf(BT_Node a);


int BT_Empty(BinaryTree a);

/**
 * @brief Calculates the size recursively.
 */
int BT_Size(BT_Node a);


void BT_SetRSon(BT_Node a, BT_Node RSon);


void BT_SetLSon(BT_Node a, BT_Node LSon);
/**
 *  @brief Sets the parent of a node accordingly to the direction. 
 */
void BT_SetP(BT_Node a, BT_Node parent, int dir);

/**
 * @warning You should not change the Key because it is the data actually stored in the tree,
 * and so, the information in the tree may be altered 
 */
void * BT_GetKey(BT_Node a);


BT_Node BT_GetRoot(BinaryTree a);

BT_Node  BT_GetRSon(BT_Node a);

BT_Node  BT_GetLSon(BT_Node a);

BT_Node BT_GetP(BT_Node a);
/**
 * @brief Get the direction in which this node is a child of his father
 * @return The direction : LEFT or RIGHT or INVALID.  
 */

int BT_GetDir(BT_Node a);

BT_Sons BT_GetSons(BT_Node a);

/**
 * @brief Traverses the tree, and do some task to each node
 *  This function may be the most usefull when working with a binary tree. It can traverse the
 * tree in PREORDER, INORDER, POSTORDER accordingly to the type. 
 * For each node it executes a BT_Task t given as parameter. 
 *  This can be used for freeing data before the free of the entire tree. 
 * @param tr The tree which will be traversed
 * @param type Can be PREORDER, INORDER, POSTORDER
 * @param t The task executed for each node
 */
void BT_Traverse(BinaryTree tr, int type, BT_Task t);
#endif

=======
/*
 *  Librarie de tipuri de date abstracte (TDA)
 
    Copyright (C) 2007  Catedra de Structuri de Date

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

/**
@file binarytree.h
@author -
@brief This header file contains the structures and functions needed to work
with binary trees (implemented using pointers to nodes)

It contains functions for creating a binary tree, adding and removing nodes,
finding nodes

TODO: + alte lucruri care urmeaza a fi decise
*/

#ifndef BINARYTREE_H_
#define BINARYTREE_H_

#include "btnode.h"

struct binarytree_adt;

typedef struct binarytree_adt *BinaryTree;

BinaryTree BT_New();

BinaryTree BT_New(const void* root_data);

BTNode BT_FindData(const void* data);

int BT_Size(BinaryTree tree);

int BT_Height(BinaryTree tree);

void BT_Delete(BinaryTree tree);

#endif /*BINARYTREE_H_*/
